\chapter{Вопрос № 26}

Помеченные деревья корневые деревья, леса. Связь между количеством помеченных корневых деревьев и помеченных корневых лесов. Комбинаторный смысл произведения эпф $xF\left(x\right)$, производной $F'\left(x\right)$ эпф, а также произведения $xF'\left(x\right)$.

\section{Корневые помеченные деревья}

Корневым помеченным деревом называется помеченное дерево в котором выделена одна из вершин, очевидно, что если $t_n$ описывает количество корневых помеченных деревьев на $n$ вершинах, а $a_n$ - количество помеченных деревьев на $n$ вершинах, то имеет место соотношение:
\begin{equation}
	t_n = n \cdot a_n
\end{equation}
Корневым помеченным лесом называется граф, каждая компонента связности которого - корневое помеченное дерево, из экспоненциальной формулы можно вывести связь между корневыми лесами и корневыми деревьями, т. е. если
\[
	T\left(x\right) = t_1 x + t_2 \frac{x^2}{2!} + t_3 \frac{x^3}{3!} + ...
\]
эпф перечисляющая корневые помеченные деревья, то
\[
	For\left(x\right) = e^{T\left(x\right)} = f_0 + f_1x + f_2\frac{x^2}{2!} + f_3\frac{x^3}{3!} + ...
\]
эпф перечисляющая корневые помеченные леса.

Также покажем еще одно соотношение:
\begin{equation}
	t_{n+1} = \left(n+1\right) f_n
\end{equation}
для этого возьмем некоторый корневой помеченный лес из $n$ вершин, затем добавим вершину и присвоим ей метку $j$ из диапазона от 1 до $n+1$, далее перенумеруем все вершины метки которых $\ge j$ увеличив на 1, наконец соединим новую вершину с корнями деревьев и получем корневое помеченное дерево. Обратное преобразование также возможно.

Теперь имеем следующее:
\[
	\begin{split}
		& For\left(x\right) = \sum_{n=0}^\infty f_n \frac{x^n}{n!} = \sum_{n=0}^\infty \frac{t_{n+1}}{\left(n+1\right)} \frac{x^n}{n!} = \frac{1}{x}\sum_{n=0}^\infty t_{n+1} \frac{x^{n+1}}{\left(n+1\right)!} = \\
		& = \frac{1}{x} T\left(x\right) = e^{T\left(x\right)}
	\end{split}
\]
откуда следует:
\[
	T\left(x\right) = x e^{T\left(x\right)}
\]

\section{Комбинаторный смысл произведения $xF\left(x\right)$}

Произведение эпф $xF\left(x\right)$ - частный случай произведения эпф функций, т. е. мы делим $n+1$ элементное множество на 2, причем в первом всего 1 элемент, а во втором оставшиеся $n$ (сделать это можно очевидно $\left(n+1\right)$ способами), затем над элементами $n$-множества совершаем некоторое комбинаторное действие $a_n$ способами, где $a_n$ - коэффициент эпф $F\left(x\right)$.

В случае деревьев это как раз и означает выбрать корень, а на оставшихся $n$ вершинах построить корневой лес.

\section{Комбинаторный смысл производной эпф $F'\left(x\right)$}

Смысл заключается в добавлении к $n$-множеству $n+1$ элемента, а затем построении на этих элементах некоторой структуры (или совершении некоторого действия) $a_{n+1}$ способом, например как связаны помеченные деревья и корневые помеченные леса? Если $\tilde T\left(x\right)$ - эпф описывающая помеченные деревья, то:
\begin{equation}
	For\left(x\right) = \tilde T'\left(x\right) \Leftrightarrow f_n = \tilde t_{n+1} = \frac{t_{n+1}}{n+1}
\end{equation}
т. е. имея корневой помеченный лес добавим к нему вершину, соединим корни с этой вершиной и получим помеченное дерево.

\section{Комбинаторный смысл эпф $xF'\left(x\right)$}

Наконец разберемся со смыслом произвдения $xF'\left(x\right)$, если обозначить через $a_n$ коэффициенты эпф $F\left(x\right)$, то:
\[
	xF'\left(x\right) = a_1x + 2a_2\frac{x^2}{2!} + 3a_3\frac{x^3}{3!} + ...
\]
т. е. мы совершаем некоторое действие над $n$ элементами, а потом выбираем из них главный (очевидно $n$ способами), в случае деревьев выбираем корнеь, тогда если $\tilde T\left(x\right)$ - эпф описывающая число помеченных деревьев, то $x \tilde T'\left(x\right)$ - эпф описывающая число корневых помеченных деревьев ($t_n = n \tilde t_n$).
